package course;

import java.util.HashSet;
import java.util.Set;

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int x){
        val = x;
        next = null;
    }
    ListNode(int x, ListNode next){
        val = x;
        this.next = next;
    }
    
}

public class LinkedList {
    public static void main(String[] args) {
        
    }
}

class SolutionLinkedList{
    /**141. 环形链表
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     */
    public static boolean hasCycle(ListNode head) {
        if(head == null) return false;
        if(head.next == head) return true;
        ListNode p1 = head, p2 = head;
        do{
            if(p1.next != null)
                p1 = p1.next;
            else
                p1 = null;
            if(p2.next!=null && p2.next.next != null)
                p2 = p2.next.next;
            else
                p2 = null;
            if(p1 == null || p2 == null)
                return false;
        }while(p1 != p2);
        return true;
    }

    /** 142. 环形链表 II 使用额外空间
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     */
    public static ListNode detectCycle1(ListNode head) {
        if(head == null) return null;
        Set<ListNode> set = new HashSet<>();
        ListNode p1 = head;
        while(!set.contains(p1)){
            if(p1.next == null)
                return null;
            else{
                set.add(p1);
                p1 = p1.next;
            }
        }
        return p1;
    }

    /** 142. 环形链表 II 不使用额外空间
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 先设置快慢指针，快走两步，慢走一步，相遇以后，快指针回到起点
     * 他们都走一步，相遇处就是入环节点
     */
    public static ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        if(head.next == head) return head;
        ListNode p1 = head.next, p2 = head.next.next;
        while(p1 != p2){
            if(p2 != null && p2.next !=null && p2.next.next != null){
                p1 = p1.next;
                p2 = p2.next.next;
            }
            else
                return null;
        }
        p2 = head;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    /**876. 链表的中间结点
     * 奇数长度返回中点，偶数长度返回下中点链表长度范围[1,100]
     */
    public static ListNode middleNode(ListNode head) {
        if(head.next == null) return head;
        if(head.next.next == null) return head.next;
        ListNode p1 = head.next, p2 = head.next.next;
        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

}

